A variety of conditions may cause a copy of a data item to become unavailable. For example, a copy of a data item will become unavailable if the storage device on which the copy resides crashes. Similarly, the copy will become unavailable if the node that has access to the storage device on which the copy resides crashes.
If only one copy of a data item exists, then the data item will become unavailable if that one copy of the data item becomes unavailable. Therefore, to increase the availability of a data item, copies of the data item may be maintained on multiple storage devices accessible to multiple nodes. Systems that maintain multiple copies of data items in this manner are referred to herein as “replicated-data systems”. Each copy of the data item is referred to herein as a “replica” of the data item. The replicas of a data item are collectively referred to as the “replica set” of the data item.
Because replicas of the same data item are spread across multiple nodes in a replicated-data system, the current version of a data item may still be available within the replicated-data system even though one or more replicas of the data item are not available. For example, if each of five nodes in a replicated-data system has a replica of the current version of a data item, then the current version of the data item is available as long as any one of the five nodes is available.
Unfortunately, within a replicated-data system, it is not always possible to keep all replicas of a data item up-to-date. For example, when an update is performed to a data item, some replicas of the data item may not be available. Under these circumstances, only those replicas that are available are updated, and the unavailable replicas become out-of-date. When the out-of-date replicas become available, those replicas continue to reflect an out-of-date state of the data item. Therefore, at any given time, some of the available replicas of a data item may be “current”, while other available replicas of the same data item are out-of-date.
When a request for a data item is received by a replicated-data system, it is not safe for the replicated-data system to satisfy the request with any available replica of the data item, since some or all available replicas of the data item may be out-of-date. Therefore, replicated-data systems need some mechanism for determining which available replicas of the data item represent the current state of the data item.
One prior technique used by replicated-data systems to ensure that requests for a data item are satisfied with the current version of the data item involves conforming to the following rules:
To Update to the Data Item:
                any update must be written to at least 50% of the total replicas in a replica set        an integer, called “version number”, is increased by one for each update        the version number for the update is stored with each updated replica        storing the version number with an updated replica is performed atomically relative to the update of the replicaTo Read the Current Version of the Data Item:        more than 50% of the total replicas in a replica set must be accessible for reading        the available replica with the largest version number is used to satisfy requests        
For example, assume that a replicated-data system maintains six replicas of a particular data item. Assume that, initially, all six replicas are current, and the current Version Number is 3. If an update occurs when three of those replicas are available, then the Version Number will be incremented to 4, and the update will be made to the three available replicas. Note that, based on the rules identified above, no update would be possible if four or more of the replicas were unavailable. After the update is made to the three available replicas, those three replicas will specify Version Number 4, while the three replicas that were unavailable will still specify Version Number 3.
Assume that, at this point, the replicated-data system receives a request to read the current version of the data item. If three or more of the replicas are not available at the time of the request, then the replicated-data system cannot satisfy the request. However, if four or more of the replicas are available, then the replicated-data system inspects all of the available replicas, and identifies the highest version number among the replicas. In this example, the highest version number would be 4. Because the replicated-data system has complied with the rules specified above, the four or more available replicas are guaranteed to include at least one replica associated with the current version (version number 4). The replicated-data system then answers the request with the value of a replica that is associated with Version Number 4.
While conformance with the rules specified above guarantee that the replicated-data system will never provide out-of-date data items, it places relatively severe restrictions on when requests can be answered. Specifically, requests for a data item cannot be answered unless more than half of the replicas of the data item are available. If half or fewer of the replicas are available, a request for the current version of the data item cannot be answered even though one or more of the available replicas may be the current version of the data item.
Based on the foregoing, it would be desirable to provide less-restrictive techniques that still guarantee that a replicated-data system will never provide out-of-date versions of data items.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.